Search Results

Documents authored by Vandevoort, Brecht

Document
Complete Volume
DOI: 10.4230/LIPIcs.ICDT.2023
LIPIcs, Volume 255, ICDT 2023, Complete Volume

Authors: Floris Geerts and Brecht Vandevoort

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
LIPIcs, Volume 255, ICDT 2023, Complete Volume
Cite as

26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 1-466, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Proceedings{geerts_et_al:LIPIcs.ICDT.2023,
  title =	{{LIPIcs, Volume 255, ICDT 2023, Complete Volume}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{1--466},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023},
  URN =		{urn:nbn:de:0030-drops-177414},
  doi =		{10.4230/LIPIcs.ICDT.2023},
  annote =	{Keywords: LIPIcs, Volume 255, ICDT 2023, Complete Volume}
}
Document
Front Matter
DOI: 10.4230/LIPIcs.ICDT.2023.0
Front Matter, Table of Contents, Preface, Conference Organization

Authors: Floris Geerts and Brecht Vandevoort

Published in: LIPIcs, Volume 255, 26th International Conference on Database Theory (ICDT 2023)

Abstract
Front Matter, Table of Contents, Preface, Conference Organization
Cite as

26th International Conference on Database Theory (ICDT 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 255, pp. 0:i-0:xvi, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{geerts_et_al:LIPIcs.ICDT.2023.0,
  author =	{Geerts, Floris and Vandevoort, Brecht},
  title =	{{Front Matter, Table of Contents, Preface, Conference Organization}},
  booktitle =	{26th International Conference on Database Theory (ICDT 2023)},
  pages =	{0:i--0:xvi},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-270-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{255},
  editor =	{Geerts, Floris and Vandevoort, Brecht},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2023.0},
  URN =		{urn:nbn:de:0030-drops-177424},
  doi =		{10.4230/LIPIcs.ICDT.2023.0},
  annote =	{Keywords: Front Matter, Table of Contents, Preface, Conference Organization}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2022.16
Robustness Against Read Committed for Transaction Templates with Functional Constraints

Authors: Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven

Published in: LIPIcs, Volume 220, 25th International Conference on Database Theory (ICDT 2022)

Abstract
The popular isolation level Multiversion Read Committed (RC) trades some of the strong guarantees of serializability for increased transaction throughput. Sometimes, transaction workloads can be safely executed under RC obtaining serializability at the lower cost of RC. Such workloads are said to be robust against RC. Previous work has yielded a tractable procedure for deciding robustness against RC for workloads generated by transaction programs modeled as transaction templates. An important insight of that work is that, by more accurately modeling transaction programs, we are able to recognize larger sets of workloads as robust. In this work, we increase the modeling power of transaction templates by extending them with functional constraints, which are useful for capturing data dependencies like foreign keys. We show that the incorporation of functional constraints can identify more workloads as robust that otherwise would not be. Even though we establish that the robustness problem becomes undecidable in its most general form, we show that various restrictions on functional constraints lead to decidable and even tractable fragments that can be used to model and test for robustness against RC for realistic scenarios.
Cite as

Brecht Vandevoort, Bas Ketsman, Christoph Koch, and Frank Neven. Robustness Against Read Committed for Transaction Templates with Functional Constraints. In 25th International Conference on Database Theory (ICDT 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 220, pp. 16:1-16:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{vandevoort_et_al:LIPIcs.ICDT.2022.16,
  author =	{Vandevoort, Brecht and Ketsman, Bas and Koch, Christoph and Neven, Frank},
  title =	{{Robustness Against Read Committed for Transaction Templates with Functional Constraints}},
  booktitle =	{25th International Conference on Database Theory (ICDT 2022)},
  pages =	{16:1--16:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-223-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{220},
  editor =	{Olteanu, Dan and Vortmeier, Nils},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2022.16},
  URN =		{urn:nbn:de:0030-drops-158905},
  doi =		{10.4230/LIPIcs.ICDT.2022.16},
  annote =	{Keywords: concurrency control, robustness, complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2019.14
Parallel-Correctness and Parallel-Boundedness for Datalog Programs

Authors: Frank Neven, Thomas Schwentick, Christopher Spinrath, and Brecht Vandevoort

Published in: LIPIcs, Volume 127, 22nd International Conference on Database Theory (ICDT 2019)

Abstract
Recently, Ketsman et al. started the investigation of the parallel evaluation of recursive queries in the Massively Parallel Communication (MPC) model. Among other things, it was shown that parallel-correctness and parallel-boundedness for general Datalog programs is undecidable, by a reduction from the undecidable containment problem for Datalog. Furthermore, economic policies were introduced as a means to specify data distribution in a recursive setting. In this paper, we extend the latter framework to account for more general distributed evaluation strategies in terms of communication policies. We then show that the undecidability of parallel-correctness runs deeper: it already holds for fragments of Datalog, e.g., monadic and frontier-guarded Datalog, with a decidable containment problem, under relatively simple evaluation strategies. These simple evaluation strategies are defined w.r.t. data-moving distribution constraints. We then investigate restrictions of economic policies that yield decidability. In particular, we show that parallel-correctness is 2EXPTIME-complete for monadic and frontier-guarded Datalog under hash-based economic policies. Next, we consider restrictions of data-moving constraints and show that parallel-correctness and parallel-boundedness are 2EXPTIME-complete for frontier-guarded Datalog. Interestingly, distributed evaluation no longer preserves the usual containment relationships between fragments of Datalog. Indeed, not every monadic Datalog program is equivalent to a frontier-guarded one in the distributed setting. We illustrate the latter by considering two alternative settings where in one of these parallel-correctness is decidable for frontier-guarded Datalog but undecidable for monadic Datalog.
Cite as

Frank Neven, Thomas Schwentick, Christopher Spinrath, and Brecht Vandevoort. Parallel-Correctness and Parallel-Boundedness for Datalog Programs. In 22nd International Conference on Database Theory (ICDT 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 127, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{neven_et_al:LIPIcs.ICDT.2019.14,
  author =	{Neven, Frank and Schwentick, Thomas and Spinrath, Christopher and Vandevoort, Brecht},
  title =	{{Parallel-Correctness and Parallel-Boundedness for Datalog Programs}},
  booktitle =	{22nd International Conference on Database Theory (ICDT 2019)},
  pages =	{14:1--14:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-101-6},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{127},
  editor =	{Barcelo, Pablo and Calautti, Marco},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2019.14},
  URN =		{urn:nbn:de:0030-drops-103165},
  doi =		{10.4230/LIPIcs.ICDT.2019.14},
  annote =	{Keywords: Datalog, distributed databases, distributed evaluation, decision problems, complexity}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2018.18
Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics

Authors: Bas Ketsman, Frank Neven, and Brecht Vandevoort

Published in: LIPIcs, Volume 98, 21st International Conference on Database Theory (ICDT 2018)

Abstract
Single-round multiway join algorithms first reshuffle data over many servers and then evaluate the query at hand in a parallel and communication-free way. A key question is whether a given distribution policy for the reshuffle is adequate for computing a given query. This property is referred to as parallel-correctness. Another key problem is to detect whether the data reshuffle step can be avoided when evaluating subsequent queries. The latter problem is referred to as transfer of parallel-correctness. This paper extends the study of parallel-correctness and transfer of parallel-correctness of conjunctive queries to incorporate bag semantics. We provide semantical characterizations for both problems, obtain complexity bounds and discuss the relationship with their set semantics counterparts. Finally, we revisit both problems under a modified distribution model that takes advantage of a linear order on compute nodes and obtain tight complexity bounds.
Cite as

Bas Ketsman, Frank Neven, and Brecht Vandevoort. Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics. In 21st International Conference on Database Theory (ICDT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 98, pp. 18:1-18:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{ketsman_et_al:LIPIcs.ICDT.2018.18,
  author =	{Ketsman, Bas and Neven, Frank and Vandevoort, Brecht},
  title =	{{Parallel-Correctness and Transferability for Conjunctive Queries under Bag Semantics}},
  booktitle =	{21st International Conference on Database Theory (ICDT 2018)},
  pages =	{18:1--18:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-063-7},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{98},
  editor =	{Kimelfeld, Benny and Amsterdamer, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2018.18},
  URN =		{urn:nbn:de:0030-drops-86040},
  doi =		{10.4230/LIPIcs.ICDT.2018.18},
  annote =	{Keywords: Conjunctive queries, distributed evaluation, bag semantics}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact